package com.code.test.second.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0077.%E7%BB%84%E5%90%88.md
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 * <p>
 * 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
 */
public class SCode77 {


    public static void main(String[] args) {
        List<List<Integer>> ret = combine(4,2);
        System.out.println(ret.size());
        System.out.println(ret);
    }


    static List<List<Integer>> ret = new ArrayList<>();
    //每个组合
    static List<Integer> temp = new ArrayList<>();

    public static List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return ret;
    }


    public static void backtracking(int n, int k, int startIndex) {
        if (temp.size() == k) {
            ret.add(new ArrayList<>(temp));
            return;
        }

        /**
         * 找到当前数字所对应的字母
         */
        for (int i = startIndex; i <=n; i++) {
            /**
             * 1,2,3,4  不能重复
             * 1 跟 2，3，4
             * 2 跟 3，4
             * 3 跟 4
             */
            temp.add(i);
            /**
             * [1] &[2,3,4]
             * [2] & [3,4]
             */

            backtracking(n, k, i + 1);
            temp.remove(temp.size() - 1);
        }

    }


}
